Implementing the Shell Sort Algorithm with Python

Shell Sort is an improved version of Insertion Sort, which enhances efficiency by "coarsely sorting" and then "finely sorting" through grouping to reduce element intervals. The core involves selecting an initial increment (e.g., half the array length), dividing the array into multiple groups where elements within each group are spaced by the increment, and applying Insertion Sort to each group. The process then repeats with the increment halved until the increment reaches 1, completing the "fine sorting." Its key logic is reducing element movement through grouping: initially grouping with large intervals allows the array to become nearly sorted first, and gradually shrinking the increment ensures the final Insertion Sort phase finishes efficiently. The average time complexity is O(n log n), worst-case O(n²), with a space complexity of O(1). Shell Sort is suitable for arrays of moderate size with uneven element distribution and is an efficient in-place sorting algorithm.